10229 - Modular Fibonacci/10229.cpp

   1 using namespace std;
   2 #include <algorithm>
   3 #include <iostream>
   4 #include <iterator>
   5 #include <sstream>
   6 #include <fstream>
   7 #include <cassert>
   8 #include <climits>
   9 #include <cstdlib>
  10 #include <cstring>
  11 #include <string>
  12 #include <cstdio>
  13 #include <vector>
  14 #include <cmath>
  15 #include <queue>
  16 #include <deque>
  17 #include <stack>
  18 #include <list>
  19 #include <map>
  20 #include <set>
  21
  22 #define foreach(x, v) for (typeof (v).begin() x = (v).begin(); x != (v).end(); ++x)
  23 #define D(x) cout << #x " is " << x << endl
  24
  25 int mod;
  26 struct matrix{
  27   //2 x 2 matrix:
  28   //a b
  29   //c d
  30   int a, b, c, d;
  31   matrix(){}
  32   matrix(int a, int b, int c, int d) : a(a), b(b), c(c), d(d) {}
  33   const matrix  operator * (const matrix &t){
  34     long long A = 1LL * a * t.a + 1LL * b * t.c;
  35     long long B = 1LL * a * t.b + 1LL * b * t.d;
  36     long long C = 1LL * c * t.a + 1LL * d * t.c;
  37     long long D = 1LL * c * t.b + 1LL * d * t.d;
  38     if (A >= mod) A %= mod;
  39     if (B >= mod) B %= mod;
  40     if (C >= mod) C %= mod;
  41     if (D >= mod) D %= mod;
  42     return matrix(A, B, C, D);
  43   }
  44 };
  45
  46 //returns p^n
  47 matrix pow(const matrix &p, int n){
  48   if (n == 1) return p;
  49   matrix k = pow(p, n/2);
  50   matrix ans = k*k;
  51   if (n & 1) ans = ans * p;
  52   return ans;
  53 }
  54
  55 int main(){
  56   int n, m;
  57   while (cin >> n >> m){
  58     mod = 1 << m;
  59     if (n == 0){ cout << 0 << endl; continue; }
  60     matrix fib = pow(matrix(0, 1, 1, 1), n);
  61     cout << fib.b << endl;
  62   }
  63   return 0;
  64 }
  65 /*
  66   It can be proved by induction that:
  67
  68  _   _ ^ n     _                   _
  69 | 0 1 |    =  |  fib(n-1)  fib(n)   |
  70 |_0 1_|       |_  fib(n)  fib(n+1) _|
  71
  72  */